692. Top K Frequent Words

#Algorithm #Algorithm-Bucket_Sort #Algorithm-Divide_N_Conquer
692. Top K Frequent Words

1. 문제

1-1. 원문

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:
Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

1-2. 내용 번역

주어진 단어들의 배열이 있을 때, 출현 빈도수가 가장 높은 단어 k개를 리턴해라.
결과 배열은 가장 높은 출현빈도별, 알파벳 순서로 정렬되어 있어야 한다.

2. 문제 이해

2-1. 내용 이해

words = ["i","love","leetcode","i","love","coding"], k = 2 이라고 하면, i가 2번, love가 2번, leetcode가 1번, coding이 1번 나왔네. 가장 출현빈도가 높은 2개는 i와 love가 각각 2번이니까 이 둘일거고, 출현빈도는 같으니까 알파벳 순서대로 정렬해서 출력하면 되겠다. 그래서 결과는 ["i", "love"]네.

2-2. 접근법 생각

출현 빈도를 알기 위해서 해시맵을 써서 카운팅해야겠다.
...
출현빈도가 같은 버킷에 있는 단어끼리는 알파벳 소팅을 하고, k번째가 포함된 버켓에서는 알파벳 소팅하고 k번째까지 잘라야지.
-> 미리 모든 버켓을 소팅할 필요는 없으니까 결과배열에 값을 담으면서 버켓별로 소팅해야겠다.

2-3. 적용한 풀이

버켓소트

3. 구현

class Solution {
    fun topKFrequent(words: Array<String>, k: Int): List<String> {
        val countingMap = HashMap<String, Int>()

        for(word in words) {
            countingMap.put(word, countingMap.getOrPut(word){0}+1)
        }

        val bucket = Array<ArrayList<String>>(words.size+1){ArrayList<String>()}

        for((word, count) in countingMap) {
            bucket[count].add(word)
        }

        var count = 0
        val resultList = ArrayList<String>()
        for(idx in bucket.size-1 downTo 0) {
            if (bucket[idx].size > 0) {
                val sortedList = bucket[idx].sorted()
                for(word in sortedList) {
                    if (count == k) return resultList
                    resultList.add(word)
                    count++
                }
            }
        }

        return resultList
    }
}

4. 복잡도